package com.jojo.elementary.day11_tree;

import com.jojo.elementary.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 104、二叉树的层序遍历
 *
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）
 *
 * 示例 1：
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 *
 * 示例 2：
 * 输入：root = [1]
 * 输出：[[1]]
 *
 * 示例 3：
 * 输入：root = []
 * 输出：[]
 *
 */
public class TreeLevelErgodic {

    /** myCode 广度优先遍历 */
    public List<List<Integer>> levelOrder(TreeNode root) {
        //结果
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        //存每层的所有节点
        List<TreeNode> tree = new ArrayList<>();
        tree.add(root);
        while (!tree.isEmpty()){
            //每层的所有数据
            List<Integer> level = new ArrayList<>();
            //临时的每层所有节点
            List<TreeNode> temp = new ArrayList<>();
            for (TreeNode treeNode : tree) {
                level.add(treeNode.val);
                if (treeNode.left != null){
                    temp.add(treeNode.left);
                }
                if (treeNode.right != null){
                    temp.add(treeNode.right);
                }
            }
            result.add(level);
            tree = temp;
        }
        return result;
    }
}
